#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <unistd.h>
using namespace std;

typedef char DataType;
struct BinaryTreeNode
{
    DataType _myValue;
    BinaryTreeNode *_lchild;
    BinaryTreeNode *_rchild;
    BinaryTreeNode *_parent;
    BinaryTreeNode(DataType value):_myValue(value),_lchild(NULL),_rchild(NULL),_parent(NULL)
    {}
};

void PreOrder(BinaryTreeNode *root)
{
    if(root==NULL)
    {
        return;
    }
    printf("%c ",root->_myValue);
    PreOrder(root->_lchild);
    PreOrder(root->_rchild);
}
void InOrder(BinaryTreeNode *root)
{
    if(NULL==root)
    {
        return;
    }
    InOrder(root->_lchild);
    printf("%c ",root->_myValue);
    InOrder(root->_rchild);
}
void PostOrder(BinaryTreeNode *root)
{
    if(NULL==root)
    {
        return;
    }
    PostOrder(root->_lchild);
    PostOrder(root->_rchild);
    printf("%c ",root->_myValue);
}
void PrintTree(BinaryTreeNode *root)
{
    printf("先序遍历结果：\n");
    PreOrder(root);
    printf("\n");
    printf("中序遍历结果：\n");
    InOrder(root);
    printf("\n");
    printf("后序遍历结果：\n");
    PostOrder(root);
    printf("\n");
}
BinaryTreeNode *_FindBinaryTreeNextInOrderNode(BinaryTreeNode *root,BinaryTreeNode *pos_e)
{
    //第一种情况：
    //该节点有右孩子，那么就找到它右孩子的最左边的节点
    if(pos_e->_rchild!=NULL)
    {
        BinaryTreeNode *ret=pos_e->_rchild;
        while(ret->_lchild!=NULL)
        {
            ret=ret->_lchild;
        }
        return ret;
    }
    //第二种情况：
    //该节点没有右子树
    //那就找到它的父节点，并且它刚好是父节点的左子树
    if(pos_e->_parent!=NULL&&(pos_e->_parent)->_lchild==pos_e)
    {
        return pos_e->_parent;
    }
    //该节点是父节点的右子树
    if(pos_e->_parent!=NULL&&(pos_e->_parent)->_rchild==pos_e)
    {
        BinaryTreeNode *ret=pos_e;
        while(ret!=root)
        {
            if((ret->_parent)->_lchild==ret)
            {
               return ret->_parent;
            }
            ret=ret->_parent;
        }
        //出循环遍历到了ret=root,说明该节点为最后一个中序遍历的节点
        return NULL;
    }
    //说明该节点为root,并且没有右子树
    return NULL;
}
BinaryTreeNode *FindBinaryTreeNextInOrderNode(BinaryTreeNode *root,BinaryTreeNode *pos_e)
{
    assert(root);
    assert(pos_e);
    return _FindBinaryTreeNextInOrderNode(root,pos_e);
}
void TestFind()
{
    printf("对普通二叉树进行测试：\n");
    BinaryTreeNode *root =new BinaryTreeNode('a');
    BinaryTreeNode *pos_b=new BinaryTreeNode('b');
    BinaryTreeNode *pos_c=new BinaryTreeNode('c');
    BinaryTreeNode *pos_d=new BinaryTreeNode('d');
    BinaryTreeNode *pos_e=new BinaryTreeNode('e');
    BinaryTreeNode *pos_f=new BinaryTreeNode('f');
    BinaryTreeNode *pos_g=new BinaryTreeNode('g');
    root->_lchild=pos_b;
    root->_rchild=pos_c;
    pos_b->_lchild=pos_d;
    pos_b->_rchild=pos_e;
    pos_c->_lchild=pos_f;
    pos_c->_rchild=pos_g;
    pos_b->_parent=root;
    pos_c->_parent=root;
    pos_d->_parent=pos_b;
    pos_e->_parent=pos_b;
    pos_f->_parent=pos_c;
    pos_g->_parent=pos_c;
    PrintTree(root);
    BinaryTreeNode *ret=FindBinaryTreeNextInOrderNode(root,pos_g);
    printf("ret:expect NULL,actual %p\n",ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_d);
    printf("ret:expect %p,actual %p\n",pos_b,ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_b);
    printf("ret:expect %p,actual %p\n",pos_e,ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_e);
    printf("ret:expect %p,actual %p\n",root,ret);
    ret=FindBinaryTreeNextInOrderNode(root,root);
    printf("ret:expect %p,actual %p\n",pos_f,ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_f);
    printf("ret:expect %p,actual %p\n",pos_c,ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_c);
    printf("ret:expect %p,actual %p\n",pos_g,ret);
}
void TestFind_All_Lchild()
{
    printf("对只有左子树二叉树进行测试：\n");
    BinaryTreeNode *root =new BinaryTreeNode('a');
    BinaryTreeNode *pos_b=new BinaryTreeNode('b');
    BinaryTreeNode *pos_c=new BinaryTreeNode('c');
    root->_lchild=pos_b;
    pos_b->_lchild=pos_c;
    pos_b->_parent=root;
    pos_c->_parent=pos_b;
    PrintTree(root);
    BinaryTreeNode *ret=NULL;
    ret=FindBinaryTreeNextInOrderNode(root,pos_c);
    printf("ret:expect %p,actual %p\n",pos_b,ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_b);
    printf("ret:expect %p,actual %p\n",root,ret);
    ret=FindBinaryTreeNextInOrderNode(root,root);
    printf("ret:expect NULL,actual %p\n",ret);
}
void TestFind_All_Rchild()
{
    printf("对只有右子树二叉树进行测试：\n");
    BinaryTreeNode *root =new BinaryTreeNode('a');
    BinaryTreeNode *pos_b=new BinaryTreeNode('b');
    BinaryTreeNode *pos_c=new BinaryTreeNode('c');
    root->_rchild=pos_b;
    pos_b->_rchild=pos_c;
    pos_b->_parent=root;
    pos_c->_parent=pos_b;
    PrintTree(root);
    BinaryTreeNode *ret=NULL;
    ret=FindBinaryTreeNextInOrderNode(root,root);
    printf("ret:expect %p,actual %p\n",pos_b,ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_b);
    printf("ret:expect %p,actual %p\n",pos_c,ret);
    ret=FindBinaryTreeNextInOrderNode(root,pos_c);
    printf("ret:expect NULL,actual %p\n",ret);
}
int main()
{
    TestFind();
    TestFind_All_Lchild();
    TestFind_All_Rchild();
    return 0;
}
